package com.example.algorithm.greedy;

import java.util.PriorityQueue;

/**
 * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 *  若可行，输出任意可行的结果。若不可行，返回空字符串。
 *
 *  示例 1:
 * 输入: S = "aab"
 * 输出: "aba"
 *
 *  示例 2:
 * 输入: S = "aaab"
 * 输出: ""
 */
public class Leetcode767_ReorganizeString {
    public static void main(String[] args) {
        String s = "aab";
        s = "aaab";
        s = "aaababaacbb";
        System.out.println(new Solution().reorganizeString(s));
    }

    static class Solution {

        /**
         * 最大堆 + 贪心算法
         * @param s
         * @return
         */
        private String reorganizeString1(String s) {
            StringBuilder sb = new StringBuilder();
            int[] counts = new int[26];
            char[] chars = s.toCharArray();
            int len = chars.length;
            if (len < 2) return s;
            // 统计每个字符出现的次数, 其中只要有一个字符的个数大于 (len + 1) / 2 说明不能重构
            for (int i = 0; i < len; i++) {
                if (++counts[chars[i] - 'a'] > (len + 1) / 2) return "";
            }

            // 使用最大堆进行重构
            PriorityQueue<Character> maxHeap = new PriorityQueue<>((c1, c2) -> counts[c2 - 'a'] - counts[c1 - 'a']);
            for (int i = 0; i < counts.length; i++) {
                if (counts[i] > 0) maxHeap.offer((char)('a' + i));
            }

            while (maxHeap.size() > 1) {
                // 每次poll出剩余个数最多的两个字符(贪心策略)，并拼接到新字符串上
                char char1 = maxHeap.poll();
                char char2 = maxHeap.poll();
                sb.append(char1).append(char2);
                // 重构最大堆
                if (--counts[char1 - 'a'] > 0) maxHeap.offer(char1);
                if (--counts[char2 - 'a'] > 0) maxHeap.offer(char2);

            }

            if (!maxHeap.isEmpty()) sb.append(maxHeap.poll());


            return sb.toString();
        }

        public String reorganizeString(String s) {
            return reorganizeString1(s);
        }
    }
}
